package com.ntd.study.algorithm.sort.impl;

import com.ntd.study.algorithm.sort.Sort;

import java.util.function.BiFunction;

/**
 * 希尔排序算法
 *
 * @author liuwenju
 * @date 2021/4/22
 */
public class SortHill<T> implements Sort<T> {

    @Override
    public T[] sort(T[] arrays, BiFunction<T, T, Boolean> sort) {
        int gap = 1;
        while (gap < arrays.length/3) {
            gap = gap * 3 + 1;
        }
        while (gap > 0) {
            for (int i = gap; i < arrays.length; i++) {
                T tmp = arrays[i];
                int j = i - gap;
                while (j >= 0 && sort.apply(arrays[j], tmp)) {
                    arrays[j + gap] = arrays[j];
                    j -= gap;
                }
                arrays[j + gap] = tmp;
            }
            gap = (int) Math.floor(gap / 3);
        }
        return arrays;
    }
}
